1.0 Field of the Invention
This invention relates to index exploitation; and in particular, this invention relates to index exploitation to process queries in a database management system.
2.0 Description of the Related Art
Database management systems allow data to be accessed quickly and conveniently. An eXtensible Mark-up Language (XML) database stores XML documents. In some XML databases, the XML documents may be organized into collections.
XML is a markup language for representing structured data. XML is also a meta-language for defining markup languages. XML is used as a format for documents, referred to as XML documents. The XML documents may be published, for example, on the World Wide Web or other networks.
A query language is used to access data in XML documents of an XML database. XQuery is one example of a query language for XML documents. In addition, extensions to the Structured Query Language (SQL) are provided in SQL/XML to allow access to data in XML documents in a database management system. In this description, any query which accesses XML documents will also be referred to as an XML query.
An XML query specifies desired data in the XML documents. The XML query typically specifies the desired data using a path expression. The path expression is typically expressed using a path language. One example of a path language is the XML Path language, which is also referred to as XPath. A path expression which is expressed using XPath is referred to as an XPath expression. An XML document can be represented as a tree structure. An XPath expression can be used to describe the location of information in an XML document based on a path through a tree structure representing the XML document.
XPath may be embedded in a host language such as XQuery or SQL/XML. XPath expressions may define a complex path through an XML document, and processing queries may be expensive in time and resources, especially when a query is performed over a large number of XML documents.
A query typically comprises at least one conditional expression. A conditional expression may use comparison operators and logical operators. Examples of comparison operators comprise less than “<”, greater than “>”, equal “=”, “greater than or equal” “≧” “less than or equal” “≦”, and “not equal” “≠”. Examples of logical operators comprise “AND”, “OR”, and “NOT”.
In one conventional relational database management system, with respect to non-XML documents, an explicit between predicate can be used to select rows of a table for which a specified column has a value that is between two other values. For example, using SQL, one syntax of an explicit between predicate is as follows:
column1 BETWEEN value1 AND value2.
In the explicit between predicate above, “column1” is a name of a column of the database table, and value1 and value2 are specified values, such as integers. The column “column1” does not contain an XML document.
For example, assume that a table named PRODUCTS has a product identifier column called ID, and a price column called PRICE. The price column contains integer values. Using SQL, a query may be specified as follows:
SELECT ID, PRICE FROM PRODUCTS                WHERE (PRICE BETWEEN 100 AND 200)        
In the above query, the expression “(PRICE BETWEEN 100 AND 200)” following “WHERE” is an explicit between predicate.
Currently, the XQuery language and the SQL/XML language do not have an explicit between predicate such as illustrated above.
Therefore, there is a need for a technique to identify and process a between predicate in an XML query. It is also desirable that this technique identify and process a between predicate which is implicitly expressed in an XML query. In addition, it is desirable that an index plan which is generated based on the between predicate of the XML query perform a single index scan of an index that is used to process the between predicate.
An XML query may specify desired data using multiple conditional expressions which are connected by “AND” and “OR” operators. At least one index may also be defined on the XML documents of a database. There is a need for a technique to process the XML query using at least one index such that a superset comprising the data that satisfies the query will be produced for further evaluation to provide the query result.
Furthermore, a given path expression of an XML query may have m conditional expressions and n indexes which can be used to process the query. Using a conventional query tree, time and resources are used traversing the query to identify those portions of the query that may be able to be processed using indexes. Therefore, there is a need for a technique to more quickly identify those portions of a query that may be processed using an index.